HashMap源码分析

发表于 | 分类于 | 阅读次数:

HashMap是最常见使用最频繁的java集合容器之一，它用来存储键值对。

继承关系及结构

1
2
3
4
public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable
`

可以看出 HashMap 继承自AbstractMap，实现了Map，Cloneable，Serializable等接口

HashMap内部由hash数组(或者叫bucket数组)和链表组成结构，链表用来解决hash冲突，hash数组的每个元素都是一个单链表的头结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable{
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    static final int MAXIMUM_CAPACITY = 1 << 30;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    static final Entry<?,?>[] EMPTY_TABLE = {};
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
    transient int size;
    int threshold;
    final float loadFactor;
    …… 

}

table为hash数组用来存储链表的头结点，theshhold为阈值，当size满足 size >= threshold 时需要对hashmap扩容，threshold = newCapacity * loadFactor,这里newCapacity为期望的新的容量大小。具体我们在扩容时说明。

Entry是HashMap存储元素的数据结构，它至少应该包含存储的键值对以及链表结构中的next节点引用

1
2
3
4
5
6
7
static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;
        ……
}

除了上面说的三个元素，Entry还包含了hash信息，这里的hash值是通过key的hashcodef进行哈希后的值。hash函数为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

感兴趣的读者可以研究下这个hash方法，它能使得添加的元素均匀的分布在hash数组中。

构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                            initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                            loadFactor);
    this.loadFactor = loadFactor;
    threshold = initialCapacity;
    init();
}

默认的情况下，HashMap的容量为16，加载因子为0.75 ，所以阈值 threshold = 16，初始情况并没有通过loadFactor计算。init的实现为空，可见在构造方法中并没有去构造table数组，只是设置了一些参数。初始化table数组的过程是在添加第一个元素的时候进行的。

添加元素

了解了HashMap的结构后，接下来就看看怎么添加元素到HashMap中，这是通过put方法来完成的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

put过程分为下面几个步骤进行：

  1. 添加第一个元素的时，table还是空的数组，这时需要通过inflateTable来初始化数组
  2. 如果key值为null,使用putForNullKey添加元素
  3. 否则通过key值计算hash值，如果key值已经存在则更新数组，否则通过addEntry添加新的键值对到map中

下面我们具体分析上面的步骤，先看数组是如何初始化的

1
2
3
4
5
6
7
8
private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);

    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

这个方法会通过roundUpToPowerOf2调整toSize，toSize为我们要设置的大小，这里调整为2的幂次方大且大于等于toSize,默认的大小一开始为16，这里调整后同样为16,然后计算阈值，通过capacity * loadFactor，当然阈值不能大于MAXIMUM_CAPACITY + 1，这里我们就明白了再构造方法中并不计算threshold，因为这里会进行真正的计算。最后会通过initHashSeedAsNeeded生成一个hash seed ，这个seed在hash中会使用，我们不用关心了解即可。

然后我们看下key为null值时HashMap是如何处理的

1
2
3
4
5
6
7
8
9
10
11
12
13
private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

可以看到当key值为null是，默认是加入table中索引为0的位置的,它的hash值也为0。如果在table[0]的链表中有key值为null的则更新value值即可，否则通过addEntry添加，最后一个参数0指定了添加到table的0索引指定的buket。

对于key值不为null的元素，首先对key进行哈希后得到hash值，通过hash值确认在table中的index位置，这个是通过indexfor完成的

1
2
3
4
static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

得到索引后，就可以通过遍历索引处的链表开始查找该元素，如果找到就更新value值，这里找到的条件为

1
e.hash == hash && ((k = e.key) == key || key.equals(k))

即hash值和key值都要匹配，key值的匹配可能会通过equals进行匹配，这也是最常见的情况。

如果未找到key值对应的Entry，需要调用addEntry添加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

如果添加元素时size值大于等于阈值且当前buket不为空则需要扩容，关于扩容我们后面再说，这里看如何为key-value创建Entry，在createEntry首先从table中取到对应的bucket,随后new一个新的Entry，同时将size加1.

1
2
3
4
5
6
Entry(int h, K k, V v, Entry<K,V> n) {
    value = v;
    next = n;
    key = k;
    hash = h;
}

可以看出，新创建的Entry是作为链表的头结点的，而之前取出的e头结点在创建Entry时候赋值给新结点的next引用，这样就是每次添加新的元素都会添加到链表的头部。

删除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public V remove(Object key) {
    Entry<K,V> e = removeEntryForKey(key);
    return (e == null ? null : e.value);
}

final Entry<K,V> removeEntryForKey(Object key) {
    if (size == 0) {
        return null;
    }

    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);
    Entry<K,V> prev = table[i];
    Entry<K,V> e = prev;

    while (e != null) {
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            modCount++;
            size--;
            if (prev == e)
                table[i] = next;
            else
                prev.next = next;
            e.recordRemoval(this);
            return e;
        }
        prev = e;
        e = next;
    }
    return e;
}

删除元素的逻辑和添加的大体上是类似的，首先通过key值计算hash值，这里需要注意当key为null时，hash值为0，随后从table中取到对应的bucket,最后遍历bucket，找到满足条件的key值，从链表中移除，并将size减1.

扩容

扩容的时候是在addEntry中进行的，这样可以分摊扩容操作的代价，具体看代码

1
2
3
4
5
if ((size >= threshold) && (null != table[bucketIndex])) {
    resize(2 * table.length);
    hash = (null != key) ? hash(key) : 0;
    bucketIndex = indexFor(hash, table.length);
}

之前我们知道了table数组大小默认为16，阈值为16*0.75=12,也就是当map大小增加到12时就要增加容量了，这里的容量是针对table数组的。而size是map的元素个数。可以看到默认情况是扩充为原来容量的2倍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

Map的容量是有大小限制的，最大为MAXIMUM_CAPACITY默认为2^30，当容量已经是最大值时不允许再扩容了，否则根据新的容量大小创建新的Entry数组，同时使用transfer将旧table中的元素转移到新的table数组中，同时根据新的容量计算阈值threshold。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

transfer会将旧table中的元素转移到新的table中,转移过程可能需要对key进行重新hash。

注意事项

由于HashMap在操作bucket时需要先对key值进行hash，而hash过程中会通过key值的hashCode进行计算，所以在针对逻辑相等的对象不仅需要实现equals方法而且也应该实现hashCode方法以保证hashcode值在逻辑上相等，否则key会被映射到不同的bucket中导致查找失败。这个在Joshua Bloch《Effective java》一书中有所强调。

坚持原创技术分享，您的支持将鼓励我继续创作！